# 二叉树的层序遍历II: https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 和 二叉树的层序遍历 解法一样，最后返回时，反转一下
class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        """
            可以直接正着求解，然后 翻转一下结果列表，这里可以使用 . 二叉树的层序遍历中提到的方法
            使用前序遍历（递归或者显示栈）解决
        """
        if not root: return []
        rst = [[]]
        def dlr(node, deep):
            if not node:
                return 

            if len(rst) < deep: rst.append([])
            rst[deep - 1].append(node.val)

            if node.left: dlr(node.left, deep + 1)
            if node.right: dlr(node.right, deep + 1)
        
        dlr(root, 1)
        return rst[::-1]



